//
//  144. 二叉树的前序遍历.swift
//  手撕code
//
//  Created by xiaoZuDeMeng on 2024/3/6.
//

import Foundation

//https://leetcode.cn/problems/binary-tree-preorder-traversal/description/
//给你二叉树的根节点 root ，返回它节点值的 前序 遍历。
//
//
//
//示例 1：
//
//
//输入：root = [1,null,2,3]
//输出：[1,2,3]
//示例 2：
//
//输入：root = []
//输出：[]
//示例 3：
//
//输入：root = [1]
//输出：[1]
//示例 4：
//
//
//输入：root = [1,2]
//输出：[1,2]
//示例 5：
//
//
//输入：root = [1,null,2]
//输出：[1,2]
//
//
//提示：
//
//树中节点数目在范围 [0, 100] 内
//-100 <= Node.val <= 100
//
//
//进阶：递归算法很简单，你可以通过迭代算法完成吗？

//二叉树的前序遍历：按照访问根节点——左子树——右子树的方式遍历这棵树，而在访问左子树或者右子树的时候，我们按照同样的方式遍历，直到遍历完整棵树。因此整个遍历过程天然具有递归的性质，我们可以直接用递归函数来模拟这一过程。


//基本解法
//前、中、后序，都是基于DFS即深度优先搜索的思路来考虑的。
//
//深度优先搜索DFS的概念：从根节点出发，沿着左子树方向进行纵向遍历，直到找到叶子节点为止。然后回溯到前一个节点，进行右子树节点的遍历，直到遍历完所有可达节点为止。
//ps： 其中左右子树的顺序可以颠倒
//
//本题目具体的实现方法有两种，一是递归，二是迭代，下面具体来看每种解法
//
//递归解法
//递归解法，三种解法高度一致，只是调整了一下访问结点的顺序
//
//前序遍历： 根左右，先访问根节点，然后递归左孩子，递归右孩子
//中序遍历： 左根右，递归左孩子，访问根节点，递归右孩子
//后序遍历： 左右根，递归左孩子，递归右孩子，访问根节点
//终止条件都是： 节点为空时返回
//
//
//
//作者：荒野
//链接：https://leetcode.cn/problems/binary-tree-preorder-traversal/solutions/1125221/dfsmo-ban-fa-shi-xian-er-cha-shu-xian-xu-lbq8/
//来源：力扣（LeetCode）
//著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

// 递归法
func preorderTraversal(_ root: TreeNode?) -> [Int] {
    var preOrderAry = [Int]()
    preOrder(root: root, arr: &preOrderAry)
    return preOrderAry
}

/// 二叉树先序遍历
/// - Parameters:
///   - root: 二叉树
///   - arr: 存储遍历顺序的数组
private func preOrder(root:TreeNode?, arr: inout [Int]) {
    guard root != nil else {
        return
    }
    arr.append(root!.val)
    preOrder(root: root!.left, arr: &arr)
    preOrder(root: root!.right, arr: &arr)
}

//迭代解法
//大部分的迭代解法，会给前、中、后序三种不同的解法，解法之间没有统一性，记忆起来很困难，这里以前序遍历为模版，提供一个高度统一的迭代解法。
//
//首先以前序遍历为基础，给出模版解法.
//
//前序遍历迭代
//DFS迭代解法中，我们一般会使用一个栈来进行辅助，基本思路是
//
//当左孩子不为空时，一直访问左子树到底部，并入栈
//左子树已经到底，栈顶元素出栈，访问其右孩子
//重复当前过程，继续访问左子树到底，直到栈为空并且当前节点为空
//
//作者：荒野
//链接：https://leetcode.cn/problems/binary-tree-preorder-traversal/solutions/1125221/dfsmo-ban-fa-shi-xian-er-cha-shu-xian-xu-lbq8/
//来源：力扣（LeetCode）
//著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
func preorderTraversal(_ root: TreeNode?) -> [Int] {
    guard root != nil else { return [] }//空拦截
    var preOrderAry = [Int]()
    var stack = [TreeNode]()//辅助栈
    var cur = root
    while stack.isEmpty == false || cur != nil {
        while cur != nil {//左子树探底
            stack.append(cur!)
            preOrderAry.append(cur!.val)
            cur = cur!.left
        }
        let tmp = stack.popLast()!//栈顶元素出栈
        cur = tmp.right// 转到右子树继续循环
    }
    return preOrderAry
}
